Network or edge biomarkers are a reliable form to characterize phenotypes or diseases. However, obtaining edges or correlations between molecules for an individual requires measurement of multiple samples of that individual, which are generally unavailable in clinical practice. Thus, it is strongly demanded to diagnose a disease by edge or network biomarkers in one-sample-for-one-individual context. Here, we developed a new computational framework, EdgeBiomarker, to integrate edge and node biomarkers to diagnose phenotype of each single test sample. By applying the method to datasets of lung and breast cancer, it reveals new marker genes/gene-pairs and related sub-networks for distinguishing earlier and advanced cancer stages. Our method shows advantages over traditional methods: (i) edge biomarkers extracted from non-differentially expressed genes achieve better cross-validation accuracy of diagnosis than molecule or node biomarkers from differentially expressed genes, suggesting that certain pathogenic information is only present at the level of network and under-estimated by traditional methods; (ii) edge biomarkers categorize patients into low/high survival rate in a more reliable manner; (iii) edge biomarkers are significantly enriched in relevant biological functions or pathways, implying that the association changes in a network, rather than expression changes in individual molecules, tend to be causally related to cancer development. The new framework of edge biomarkers paves the way for diagnosing diseases and analyzing their molecular mechanisms by edges or networks in one-sample-for-one-individual basis. This also provides a powerful tool for precision medicine or big-data medicine.